/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
  // 递归回溯
    void traversal(TreeNode* cur, vector<int>& path, vector<int>& result){
        path.push_back(cur->val);
        if(cur->left == nullptr && cur->right == nullptr){ // 说明cur是叶子节点，返回
            int sum = 0;
            int digital = 1;
            for(int i = path.size()-1; i >= 0; --i){
                sum += path[i] * digital;
                digital *= 10;
            }
            result.push_back(sum);
            return;
        }
        // 回溯  
        if(cur->left != nullptr){
            traversal(cur->left, path, result);
            path.pop_back();
        }
        if(cur->right != nullptr){
            traversal(cur->right, path, result);
            path.pop_back();
        }
        
    }
    
    int sumNumbers(TreeNode* root) {
        if(nullptr == root) return 0;
        vector<int> p;
        vector<int> res;
        traversal(root, p, res);
        int sum = 0;
        for(int i = 0; i < res.size(); ++i)
            sum += res[i];
        return sum;
    }
};